1. Field of the Invention
This invention relates to the field of data memories, and more particularly relates to techniques for efficient routing of data through a data communication network.
2. Description of the Related Art
A data communications network is the interconnection of two or more communicating entities (i.e., data sources and/or sinks) over one or more data links. A data communications network allows communication between multiple communicating entities over one or more data communications links. High bandwidth applications supported by these networks include streaming video, streaming audio, and large aggregations of voice traffic. Data communication systems use a number of different known protocols. One protocol for high speed communication is a synchronous optical network (SONET) protocol. Another protocol commonly used in local area networks (LAN), is a Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol. One version of the CSMA/CD protocol is the IEEE 802.3 standard referred to as Ethernet. Ethernet networks typically include network equipment that transmits the data packets arranged in frames across various paths. At junctions in a network path, routers or switches handle the data. Typically, each router or switch applies one or more filters, each implemented as an Access Control List (ACL) to each packet received to determine how to handle the packet. For uses herein, an ACL refers to both an “Access Control List” and to an “Action Control List” and, where appropriate, embodiments described herein are not limited to an “access”.
In general, an ACL is a list of true/false tests that are applied to fields in a packet, and associated actions in the event that a test is determined to be true. Each test or entry in an ACL is referred to as an Access Control Entry (ACE). An ACL may be viewed as a set of ACEs that define and execute permissions. An ACL typically may also provide data including an array of ACEs, and a count of the number of ACEs in the ACL. An ACL may have one or more ACEs, with each ACE including a permission access type, such as allowed, denied, or other relevant access types.
An ACE entry may contain members that specify the type of the ACE, the action to be taken when the ACE is matched, and a description of the “match condition” for the ACE. The match condition is generally represented as a value and mask for certain fields in a packet header, although other match conditions are possible, such as specifying a numerical range of allowable values for some field in the packet header. Each ACE also specifies a “continuation” action that is used when a packet matches the ACE's match condition. There are two possible values for the continuation condition: “terminate” and “skip”. If the action is “terminate” then processing stops immediately and subsequent ACLs are not considered. If the action is “skip,” then the action associated with the current ACL is taken and processing resumes at the next ACL in the ACL list, looking for the first matching ACE in that list. The continuation is not generally specified directly by the user; rather, it is typically an implied property based on the specific Action type of the ACE. A “Security Deny” action in the prior art has an implied continuation action of “terminate” to indicate that the packet should be summarily dropped and no further action should be taken. An ACE whose action is “Security Permit and Log” would have a continuation action of “skip” to indicate that processing should continue with the next ACL in the ACL list. The “skip” continuation action is used to allow multiple higher-level functions (for example, security logging and redirection to a web cache) to be applied to a single packet.
An ACE entry may further be limited to four parts, such as a test, an action, an action continuation, and a “hit counter” type statistics parameter. A test may be a Boolean expression specified in terms of the fields in a packet, for example, the Boolean expression may be a field in a packet header such as the IP source address destination address and a port number, for a higher layer protocol such as TCP or UDP. The test returns a true or false. An action on an ACE may include dropping a packet immediately, permitting a packet to be forwarded, or redirecting a packet to some element of a router or to a separate device for special processing such as encryption, logging of the packet, translating network addresses, or performing intrusion detection. An element of a router that performs the special processing may be, for example, a line card, a processor, or an external device.
ACLs provide for a packet filtering capability. An ACL specifies a set of tests to be applied to a packet and an associated action or set of actions to be taken when a test returns true. The packet filtering capability is used, among other things, to enforce a security policy that prevents unwanted or unsafe packets from passing through a network device where the ACL has been applied. An ACL can be used to restrict or grant access to the packets sent to or from a particular user, network host, group of users, or group of network hosts. In one respect, ACLs are ordered sets of ACEs. Several ACLs may be instantiated at the same time with the same ACE appearing in two different ACLs because ACEs are not shared between ACLs. The sequence in which ACLs are applied is determined according to a plurality of methods. In general, for example, a sequence of ACLs must apply “skip” entries in the ACL that direct skipping to a next ACL to look for a matching entry.
Referring to FIG. 1, a diagram 100 illustrates the relation between ACLs and ACEs. Each ACL is given a name 110. Each ACL 120, 130 and 140 includes a plurality of ACEs. ACL 120 includes ACEs 150(1); ACL 130 includes ACES 150(2); and ACL 140 includes ACEs 150(3).
A Content Addressable Memory (CAM) may be used to process ACLs. A CAM is a specialized memory device that is used for fast searches of data stored therein. In some networking systems, CAMs are used for a plurality of purposes. For example, a CAM may be used to store a switch port associated with a specific IEEE 802.3 host address in an IEEE 802.1d bridge. Additionally, a CAM can be configured to receive data representing Action Control Lists (ACLs) and operate on them. Generally, a CAM's architecture includes a table of memory cells to store data and control logic to search and compare the data in the table. To search for data, a system provides the data to be searched and the control logic of the CAM performs the search and provides search results to the system. Two types of CAMs are binary CAMs and Ternary CAMs (TCAMs). A binary CAM searches for and recognizes data that is comprised of bits that can have two states, 0 and 1. In general a TCAM searches for and recognizes three states: 0, 1, and X (“don't care”). Also, TCAMs can be configured to search for matching entries in a network environment. For example, if provided a pattern of 0s and 1s, the TCAM can search for a matching entry. Each entry in a TCAM may be individually configured such that different degrees of a match are acceptable, i.e., such that some of the bits of the entries are “don't care” bits, thereby allowing the TCAM to ignore some of the fields in the packet while matching an entry.
A TCAM is one type of CAM that provides hardware support for evaluating ACLs. Prior to being stored in a TCAM, however, ACLs require processing and reorganization. Translating multiple ACLs presents difficulties for matching entries using a TCAM, which matches a binary string presented as an input with each row of the TCAM. In particular, an important translation that must happen is that a sequence of ACLs must be translated into an equivalent single ACL due to the inability of a TCAM to process a “skip” entry. TCAMs do not support skipping over a section of the TCAM to continue processing later in the TCAM. An ACL with an ACE providing for such a “skip” requires that any remaining action in an ACL be skipped and the next ACL on an interface be processed. Examples of ACE entries that are skip entries include a permit entry on a security-type ACL, such an entry may have an associated action, for example “permit log,” indicating to permit the packet for further processing and to record in a packet “log” that this packet arrived. In contrast, a “deny” ACE in a security-type ACL or a “permit” ACE in a feature-type ACL are types of “terminal” ACLs. A terminal ACE terminates processing immediately with some action when a match is detected. Prior art methods of merging ACEs of one or more ACLs lose the ability to track the number of matches detected by the TCAM related to the original ACLs, along with other statistics related to any user-specified ACLs. For purposes of this disclosure, “statistics” refers to data concerning the operation of an ACL and the ACE entries therein. For example, as one of ordinary skill in the art will appreciate, a known statistic is the data stored in a “hit counter” or “match counter” and variations of a “hit counter,” for example, a counter of matches within a particular time period or a counter of bytes.
The speed at which the ACL comparison can be done is often a key factor in determining the overall packet forwarding rate of a router. For example, according to prior art methods, if a router applies two ACLs to every packet, then the router requires either two TCAMs operating in parallel or every packet must be passed twice through a single TCAM. Neither of the prior art solutions are efficient because using a same TCAM twice per packet effectively halves the forwarding rate of the device. And, requiring two TCAMs dramatically increases hardware costs of the router by requiring an extra TCAM and associated board space, increased power usage, and increased pin count.
Thus, there is a need to combine ACLs into a single ACL that preserves statistics and the order in which the ACEs are performed. What is needed is a system and method that transforms a plurality of ACLs into a single ACL and efficiently reduces the number of actions performed and takes into account the statistics of the ACLs.